Atcoder abc173 题解

众所周知,abc题解不会有abc的
本场链接:https://atcoder.jp/contests/abc173
不会还是提一下C,C实际上只是一个爆搜,但是没必要修改棋盘状态,标记某一列某一行有没有被覆盖再统计就可以了,一共四种修改方案直接写dfs就好。

D:
题目大意:有nn个人,每个人有一个友好值AiA_i,每个人进入的时候,会获得坐的位置两边的两个人的友好值中较小的舒适值,并且所有人会坐成一个环。第一个人没有舒适值,并且新来的位置可以插入到环中,问最后能获得多大的舒适值总和。
注意每个人进来的顺序不是固定的,并且位置可以插入原有的两个人之间。
题目范围:
2N21052 \leq N \leq 2*10^5
1Ai1091 \leq A_i \leq 10^9

分析

注意到每个人来的顺序不是固定的,而且第一个人是拿不到舒适值的,可以想到第一个人一定是AiA_i最大的人,因为假如第二个人较小则获得的收益降低,若相同则不影响,结果不会变差。

其次可以拓展出整个过程肯定也是先选大的进去比较好,所以整个序列的编排顺序应该是从大到小依次插入的。每次应该选择整个序列中次大的值。由于可以插入到任意位置之间,这导致一个人实际上可以用两次,因为这个人会有两个相邻的人在,就可以放在两边算两次了(可以画图辅助理解一下)。

因此我们维护一个优先队列即可:第一权值是本身的值AiA_i,第二权值是当前使用过的次数,假如次数是00的话,那么还可以入队一起,否则就直接不管,踢出队列不加回来。每次对新的AiA_i查询次大值即可。

到这里实际上还不能完整做完本题。首先对于第二个人来说它来检测的时候肯定就没有次大值,这个时候可能就要特判掉他(之前就加入)这个时候就有一个坑点了,最大值的那个人次数不能是00而应该是11,因为这个最大值是被第二个人用过的,如果不加会WAWA掉两个点。最后记得开LL就行。

代码 [D solution]: https://atcoder.jp/contests/abc173/submissions/15010878

E:
题目大意:给NN个数的一个数列,从中选出KK个数,使总乘积最大。结果对109+710^9+7取余。
数据范围:
1N21051 \leq N \leq 2*10^5
Ai109|A_i| \leq 10^9
(本题有网上原题)

分析

首先肯定是排个序,完了之后肯定要从两边去选(存在负数的问题)。可以发现,由于负数是两两选择的,我们也同样可以在正数的选择策略上选择同样的方式。即排序之后从两边两两选择。
假如说kk是个奇数,首先削掉AnA_n,最大的肯定要选进去。假如说最大的都是负数,则后面的肯定也要选一个负数乘积出来,特殊标记一下。

之后两两选数,从起点和末尾分别开始,选两边较大的一对数加入答案,由于说有上面的特殊标记的问题,所以两边算出来的乘积需要再乘上特殊标记,因为在有标记的时候是要找出负数最小的乘积,反之则是最大的。注意一下就行。正确性比较显然,削掉奇数的情况之后两两选择也肯定能选完。

不过本题还涉及到负数取余的问题,注意在最后把resres取余调回正数就可以了。

代码 [E solution]: https://atcoder.jp/contests/abc173/submissions/15015304

F:
题目大意:给定一颗NN节点的树,定义函数F(L,R)F(L , R)为把树上所有编号在[L,R][L , R]之间的留下,并保留他们之间的边,剩余的联通块的数量。最终答案为L=1NR=LNF(L,R)\sum_{L=1}^N\sum_{R = L}^N F(L ,R)
数据范围:
1N21051 \leq N \leq 2*10^5
1u,vN1 \leq u , v \leq N
(本题也有原题,只不过是另外一题是完整的链,这题是个树,但不影响)
另外一题链接:https://codeforces.com/contest/1151/problem/E
那一场的题解:

分析

这个式子想拆看着也很难拆,又是两个求和,考虑算单个贡献。
第一个比较容易想到的结论就是:联通块的数量=点数 - 边数。由于范围特别大,只能说遍历一下每个点,于是顺理成章的我们来考虑单个点xx对整个答案的贡献是怎样的。
首先对于点数,假如说xx产生了贡献,那么他对某个产生了贡献的区间满足LxRL \leq x \leq R,进而可以算出对于单个点来说他一共会对点数产生x(nx+1)x * (n - x + 1)的贡献。
其次对于边数,假如说当前的边连接的两个分别是uuvv,那么这个边产生贡献,当且仅当uuvv都产生了贡献时,也就是说他俩都被算进图里的时候才会有贡献。那么下界肯定是较小者,上界是较大者,假设u<vu < v(否则可以交换),那么产生的边的贡献就是u(nv+1)u *(n - v +1),分别计算点数和边数贡献,最终就可以求的答案了。

代码 [F solution]: https://atcoder.jp/contests/abc173/submissions/15036598